1. Field of the Invention
This invention relates generally to forward error correction (FEC) systems, and in particular to a concatenated code, based forward error correction (FEC) system.
2. Description of the Related Art
Digital electronic systems store and transmit copious amounts of information. Storage or transmission of digital information sometimes results, however, in corruption of some of the data or payload. Defects in a storage media, or errors in the reading and writing of data from a storage media, may result in data errors. Similarly, transmission of data through a transmission channel may result in errors, through noise in the transmission channel or the inability of the transmitting or receiving unit to properly transmit or read data. As data storage and data transmission may be viewed as transmitting data to a media using a transmitting unit, and thereafter reading the data using a receiving unit, the remaining discussion will be in terms generally of data transmission. However, the utility of this invention extends to other error correction applications including, but not limited to, optical and electronic data storage systems, digital cable television systems and high definition television.
Forward error correction (FEC) is often used to increase data reliability. Generally speaking, FEC systems encode data using an encoder at a transmitter and decode data using a decoder at the receiver. During encoding, redundant information is added to the data. The redundant information allows determination by receiving units as to whether or not corruption of received data has occurred, and if so, identifies the particular data that has been corrupted and corrects the data. The redundant coded information allows the data to be corrected but within certain limits. The FEC decoder generally decodes the data, generates an error polynomial, and uses the error polynomial to determine corrections to be applied to the data.
The encoded data is generally grouped in terms of codewords. One type of codes falls in a category of block codes where a codeword is comprised of n symbols, of which k symbols are information symbols. Block coding consists of adding n-k redundancy symbols to k information symbols originating from source encoding at a transmitter and the redundancy symbols are utilized at a receiver to correct certain transmission errors. The codeword, therefore, contains n-k redundant symbols. The symbols are data words comprised of m bits. In a systematic encoding system, the n-k redundant symbols are appended to the information symbols, while in a non-systematic code the information symbols are also modified. For instance, for BCH codes, n=2m−1 and k=n−mt. To correct t bits within the codeword, mt bits of overhead/redundancy is needed. Each of the k and n symbols is made of 1 bit. For Reed-Solomon (RS) codes, n=2m−1 and k=n−2t. For RS codes, to correct t symbols within the codeword, 2t symbols of redundancy are needed. Each of the k and n symbols comprise m bits.
In the error correction process, error multiplication is possible. This occurs when enough errors are introduced to a codeword where the codeword more closely resembles another valid codeword than the originally transmitted codeword. The distance between valid codewords is known as the minimum distance dmin of the code and is given the value of 2t+1. For small values of t and/or high error rate transmissions, error multiplication becomes more prevalent.
In order to increase data transmission reliability, increased numbers of redundant symbols are required. The use of additional redundant symbols, however, decreases the effective bandwidth of a transmission system or reduces the total amount of storage space available in a storage system. Moreover, the use of additional redundant symbols increases the amount of processing and processing time performed by both the transmitting unit and the receiving unit to create or interpret the redundant symbols.
Moreover, different coding schemes have different abilities to correct different types of errors. For example, errors may be randomly distributed in a data set, or the errors may be grouped together, i.e. be burst or clustered errors. Generally speaking, increasing the number of bits within a symbol increases the ability of an FEC system to correct burst errors. However, increasing the number of bits per symbol also increases encoding and decoding circuit size and power requirements since the codeword becomes longer.
A method for achieving higher performance of forward error correction codes without the use of very long codes is to use a family of codes known as concatenated codes which is illustrated in system 10 of FIG. 1. Concatenation of two error correcting codes utilizes an inner encoder or decoder and an outer encoder or decoder where the terms, “inner” and “outer” have reference to physical location of the encoders in the transmission system relative to the communication channel. A block code, such as a Reed-Solomon (RS) code may be deployed as the outer code and another block code, such as a Bose-Chaudhuri-Hocquenghem (BCH) code may be deployed as the inner code. For background relative to concatenation coding, see the book of Shu Lin and Daniel Costello entitles, “Error Control Coding: Fundamentals and Applications”, pp. 278–280, Prentice Hall, 1983 and the book of Richard Blahut entitled, “Theory and Practice of Error Control Codes”, pp. 198–201, Addison-Wesley Publishing Company, 1983. Also, see the more recent book on coding of Irving S. Reed and Xuemin Chen entitled, “Error Control Coding for Data Networks”, Kluwer Academic Publishers, 1999.
As shown in FIG. 1 with concatenated encoders 11 and 13 where outer encoder 11 has a non-binary code (n2, k2) and is coupled, via line 12, to inner encoder 13 which has a binary code (n1, k1). The output of encoder 13 on line 14 is connected to the transmission channel 15 and received by a receiver via line 16 comprising concatenated decoders 17 and 19 where inner decoder 17 decodes binary code (n1, k1) and outer decoder 19 decodes non-binary code (n2, k2).
Concatenation coding is a particular method for constructing long codes from shorter codes. A simple concatenated code is formed from two codes: an (n1, k1) binary code C1 and an (n2, k2) non-binary code C2. Usually, C2 is a non-binary code such as Reed-Solomon and C1 is a binary BCH code. A k1k2 grouping of information bits are to be encoded. The k2 symbols of C2 are represented by their corresponding symbols of k1 binary symbols. If the minimum distance of the inner and outer codes is d1 and d2 respectively, the minimum distance, dmin, of the concatenated code is at least d1d2. Relative to non-binary block codes, see Shu Lin et al., supra, pages 170–177.
FIG. 1 illustrates the typical encoding process which consists of two steps. The k2 symbols are encoded according to the rules for C2 to form an n2 symbol code vector. Second, the k2 symbols are divided into k1 symbol groups and encoded as an n1 symbol code vector according to the rules for C1. These n1n2 digits are then transmitted one C1 vector at a time in succession into transmission channel 15.
The decode process is also a two step process typically always beginning with the inner code first. Decoding is performed for each C1 code vector as it arrives, and the check digits are removed, leaving a sequence of n2k1 digits. These symbols are then decoded according to the method for C2 resulting in the final corrected information message (k1k2).
Concatenated codes are effective against a mixture of random and burst errors. The pattern of bytes that are not correctable by the C1 code must form a correctable pattern for C2 if the concatenated code is to correct the error pattern. Scattered errors are generally corrected by C1. Bursts may affect relatively few bytes in the data stream but probably so badly that the inner code C1 cannot correct them; these few bytes of errors can be corrected by C2. Thus, C1 is effective for random distributed errors and C2 is effective for burst or clustered errors.